class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        node = ListNode(-5001)
        node.next = head
        prev = node
        base = node
        node = head
        while node:
            if node.val < prev.val:
                first = base
                while first.val < node.val:
                    first_prev = first
                    first = first.next
                node_next = node.next
                first_prev.next = node
                node.next = first
                prev.next = node_next
                node = node_next
            else:
                prev = node
                node = node.next
        return base.next
